package com.gupao.alg.alg0;

import java.util.*;

public class Topic4_BitTreeTravel {
    public static void main(String[] args) {
        BinaryTree bTree = new BinaryTree();
        bTree.root = bTree.buildBinaryTreeComplex();
//        bTree.root = bTree.buildBinaryTree();
        List<Integer> res = postorderTraversal(bTree.root);
        int testMethod = 2;
        System.out.println(res);
//        //基本遍历
//        switch (testMethod) {
//            case 1://前序
//                preOrderRecur(bTree.root);
//                break;
//            case 2:
//                inOrderRecur(bTree.root);
//                break;
//            case 3:
//                postOrderRecur(bTree.root);
//                break;
//        }

//        List<Integer> res = new ArrayList<Integer>();
//        switch (testMethod) {
//            case 1://前序
//                preOrder(bTree.root, res);
//                break;
//            case 2:
//                inOrder(bTree.root, res);
//                break;
//            case 3:
//                postOrder(bTree.root, res);
//                break;
//        }
//        System.out.println(res);
    }

    /**
     * 基本的前序遍历
     *
     * @param head
     */
    public static void preOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        System.out.print(head.val + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /**
     * 基本的中序遍历
     *
     * @param head
     */
    public static void inOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.val + " ");
        inOrderRecur(head.right);
    }

    /**
     * 基本的后序遍历
     *
     * @param head
     */
    public static void postOrderRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.print(head.val + " ");
    }

    /**
     * 前序遍历，将结果返回到list中
     *
     * @param root
     * @param res
     */

    public static void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        postOrder(root.left, res);
        postOrder(root.right, res);

    }

    /**
     * 中序遍历，将结果返回到list中
     *
     * @param root
     * @param res
     */

    public static void inOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }

        postOrder(root.left, res);
        res.add(root.val);
        postOrder(root.right, res);

    }

    /**
     * 后序遍历，将结果返回到list中
     *
     * @param root
     * @param res
     */

    public static void postOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);
    }


    /**
     * @param root
     * @return
     */

    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;


    }

}
